{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Global and Local Inversions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isIdealPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全局倒置与局部倒置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，表示由范围 <code>[0, n - 1]</code> 内所有整数组成的一个排列。</p>\n",
    "\n",
    "<p><strong>全局倒置</strong> 的数目等于满足下述条件不同下标对 <code>(i, j)</code> 的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; n</code></li>\n",
    "\t<li><code>nums[i] &gt; nums[j]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>局部倒置</strong> 的数目等于满足下述条件的下标 <code>i</code> 的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; n - 1</code></li>\n",
    "\t<li><code>nums[i] &gt; nums[i + 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>当数组 <code>nums</code> 中 <strong>全局倒置</strong> 的数量等于 <strong>局部倒置</strong> 的数量时，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,2]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>有 1 个全局倒置，和 1 个局部倒置。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,0]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>有 2 个全局倒置，和 1 个局部倒置。\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; n</code></li>\n",
    "\t<li><code>nums</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "\t<li><code>nums</code> 是范围 <code>[0, n - 1]</code> 内所有数字组成的一个排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [global-and-local-inversions](https://leetcode.cn/problems/global-and-local-inversions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [global-and-local-inversions](https://leetcode.cn/problems/global-and-local-inversions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2]', '[1,2,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        for i, x in enumerate(nums):\n",
    "            if abs(i - x) > 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        关键条件:数组nums长度为n,并且数字是由0到n-1构成的.\n",
    "        用前缀最大值的思路来判断全局倒置\n",
    "        eg: nums=[0,3,2,4,1], 对于2来说,到它为止的最大值是3,\n",
    "        它的前缀后面还有2个位置可以放置数字, nums中最大的数字是4,\n",
    "        那么4必定在2的后面,所以肯定剩下的另一个位置就是比2小的数, \n",
    "        形成一个全局倒置情况\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        curMax = 0\n",
    "        ttl = part = 0\n",
    "        for i, num in enumerate(nums[:-1]):\n",
    "            curMax = max(curMax, nums[i])\n",
    "            # 判断局部倒置\n",
    "            if nums[i] > nums[i+1]:\n",
    "                part += 1\n",
    "            # 判断全局倒置\n",
    "            behindPos = n - i - 1  # 当前数字后面还有几个空位\n",
    "            biggerNum = n-1 - curMax  # 比当前数字大的数字还有几个没有出现过\n",
    "            ttl += behindPos - biggerNum\n",
    "        \n",
    "        return ttl == part\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        return all(abs(x - i) <= 1 for i, x in enumerate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return True\n",
    "        tmp = nums[-1]\n",
    "        for i in range(n-3, -1, -1):\n",
    "            if nums[i] > tmp:\n",
    "                return False\n",
    "            tmp = min(tmp, nums[i+1])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        关键条件:数组nums长度为n,并且数字是由0到n-1构成的.\n",
    "        用前缀最大值的思路来判断全局倒置\n",
    "        eg: nums=[0,3,2,4,1], 对于2来说,到它为止的最大值是3,\n",
    "        它的前缀后面还有2个位置可以放置数字, nums中最大的数字是4,\n",
    "        那么4必定在2的后面,所以肯定剩下的另一个位置就是比2小的数, \n",
    "        形成一个全局倒置情况\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        curMax = 0\n",
    "        ttl = part = 0\n",
    "        for i, num in enumerate(nums[:-1]):\n",
    "            curMax = max(curMax, nums[i])\n",
    "            # 判断局部倒置\n",
    "            if nums[i] > nums[i+1]:\n",
    "                part += 1\n",
    "            # 判断全局倒置\n",
    "            behindPos = n - i - 1  # 当前数字后面还有几个空位\n",
    "            biggerNum = n-1 - curMax  # 比当前数字大的数字还有几个没有出现过\n",
    "            ttl += behindPos - biggerNum\n",
    "        \n",
    "        return ttl == part\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        m=nums[0]\n",
    "        if len(nums)<3:\n",
    "            return True\n",
    "        for i in range(2,len(nums)):\n",
    "            if m>nums[i]:\n",
    "                return False\n",
    "            m=max(m,nums[i-1])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: list[int]) -> bool:\n",
    "        # if len(nums) < 3:\n",
    "        #     return True\n",
    "        x = nums[0]\n",
    "        for i in range(2, len(nums)):\n",
    "            x = max(x, nums[i-2])\n",
    "            if x > nums[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\r\n",
    " \r\n",
    "        for i,n in enumerate(nums):\r\n",
    "            if i-1<=n<=i+1:\r\n",
    "                continue\r\n",
    "            else:\r\n",
    "                return False\r\n",
    "        return True\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        for i, num in enumerate(nums):\n",
    "            if abs(num-i) > 1:\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(nums) - 1: \n",
    "            if nums[i] > nums[i + 1]: \n",
    "                nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "                i += 1\n",
    "            i += 1    \n",
    "        for i in range(len(nums) - 1):         \n",
    "            if nums[i] > nums[i + 1]: \n",
    "                return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == i:\n",
    "                continue\n",
    "            elif nums[i] == i+1:\n",
    "                if nums[i+1] == i:\n",
    "                    nums[i+1] = i+1\n",
    "                    continue\n",
    "                return False\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        minimum = nums[-1]\n",
    "        for i in range(len(nums)-2, 0, -1):\n",
    "            if nums[i-1]> minimum:\n",
    "                return False\n",
    "            minimum = min(minimum, nums[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        flag = -1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]!=flag and nums[i]!=i:\n",
    "                if nums[i+1] != i or nums[i]!=i+1: return False\n",
    "                flag = i\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     if abs(num-i) > 1:\n",
    "        #         return False \n",
    "        # return True\n",
    "\n",
    "        # -----------------------\n",
    "        # return all(abs(x-i) <= 1 for i, x in enumerate(nums))\n",
    "\n",
    "        # ------------------------\n",
    "        max_val = -inf \n",
    "        for i in range(2, len(nums)):\n",
    "            if (max_val := max(max_val, nums[i-2])) > nums[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        for i,x in enumerate(nums):\n",
    "            if abs(x - i) > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if abs(nums[i] - i) > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        return all(abs(x - i) <= 1 for i, x in enumerate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        # 全局倒置一定是局部倒置\n",
    "        # 问题转化为，如何让数组没有全局倒置\n",
    "        maxn = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i + 1 < n and maxn > nums[i + 1]:\n",
    "                return False\n",
    "            maxn = max(maxn, nums[i])\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # max_list = []\n",
    "        tmp = -1\n",
    "        for i in range(2,n,1):\n",
    "            tmp = max(tmp,nums[i-2])\n",
    "            if nums[i]<tmp:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        for i in range(len(nums)):\n",
    "            if abs(nums[i] - i) > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 2:\n",
    "            return True\n",
    "        maxNum = nums[0]\n",
    "        for i in range(2, len(nums)):\n",
    "            if nums[i] < maxNum:\n",
    "                return False\n",
    "            maxNum = max(maxNum, nums[i-1])\n",
    "            \n",
    "        return True\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        mx=0\n",
    "        n=len(nums)\n",
    "        for i in range(2,n):\n",
    "           if i>=2:\n",
    "               if nums[i-2]>nums[mx]:\n",
    "                  mx=i-2\n",
    "           if nums[i]<nums[mx]:\n",
    "               return False        \n",
    "        \n",
    "        return True            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        mx=nums[0]\n",
    "        for i in range(2,len(nums)):\n",
    "            if mx>nums[i]:\n",
    "                return False \n",
    "            mx=max(mx,nums[i-1])\n",
    "        return True \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        min_ = float('inf')\n",
    "\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] >= min_:\n",
    "                return False\n",
    "            \n",
    "            min_ = min(min_, nums[i + 1])\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        关键条件:数组nums长度为n,并且数字是由0到n-1构成的.\n",
    "        用前缀最大值的思路来判断全局倒置\n",
    "        eg: nums=[0,3,2,4,1], 对于2来说,到它为止的最大值是3,\n",
    "        它的前缀后面还有2个位置可以放置数字, nums中最大的数字是4,\n",
    "        那么4必定在2的后面,所以肯定剩下的另一个位置就是比2小的数, \n",
    "        形成一个全局倒置情况\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        ttl = part = 0\n",
    "        curMax = 0\n",
    "        for i in range(n-1):\n",
    "            curMax = max(curMax, nums[i])\n",
    "            if nums[i] > nums[i+1]:\n",
    "                part += 1\n",
    "            behindPos = n - i - 1\n",
    "            availableNums = n-1-curMax\n",
    "            ttl += behindPos - availableNums\n",
    "\n",
    "        return ttl == part\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        min_suf = nums[-1]\n",
    "        for i in range(len(nums) - 2, 0, -1):\n",
    "            if nums[i - 1] > min_suf:\n",
    "                return False\n",
    "            min_suf = min(min_suf, nums[i])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\r\n",
    "        mx = 0\r\n",
    "        for i in range(2, len(nums)):\r\n",
    "            if (mx := max(mx, nums[i-2])) > nums[i]:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] > nums[i + 1] and (nums[i + 1] != i or nums[i] != i + 1):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "    n = len(nums)\n",
    "    bit = BinaryIndexedTree(n)\n",
    "    count1 = 0\n",
    "    for x in nums:\n",
    "      count1 += bit.query_range(x + 1, n)\n",
    "      bit.add(x + 1, 1)\n",
    "    count2 = 0\n",
    "    for i in range(n - 1):\n",
    "      count2 += nums[i] > nums[i + 1]\n",
    "    return count1 == count2\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  # 第i（从1开始）位加上x\n",
    "  def add(self, i, x):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += x\n",
    "      i += i & -i\n",
    "  # [1, i] 区间和\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "  # [l, r]区间和\n",
    "  def query_range(self, l, r):\n",
    "    return self.query(r) - self.query(l - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] != i and nums[i] != i - 1 and nums[i] != i + 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == i:\n",
    "                pass\n",
    "            elif nums[i] == i+1:\n",
    "                if nums[i+1] == i:\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "            elif nums[i] > i+1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        m=nums[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            if nums[i-1]>m:\n",
    "                return False\n",
    "            m=min(m,nums[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        # 只要存在nums[i] > nums[i+1]之后的值，就返回false\n",
    "        mv = nums[-1]\n",
    "        for i in range(len(nums)-3, -1, -1):\n",
    "            if nums[i] > mv:\n",
    "                return False\n",
    "            mv = min(mv, nums[i + 1])\n",
    "        return True\n",
    "    def isIdealPermutation2(self, nums: List[int]) -> bool:\n",
    "        # 只要存在一个不属于局部倒置的全局倒置就返回false\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+2, n):\n",
    "                if nums[i] > nums[j]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        for i, n in enumerate(nums):\n",
    "            if abs(n - i) <= 1:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        M = 0\n",
    "        for i in range(0, len(nums) - 2):\n",
    "            M = max(M, nums[i])\n",
    "            if nums[i + 2] < M: return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        # 全局倒置一定是局部倒置\n",
    "        # 问题转化为，如何让数组没有全局倒置\n",
    "        return all(abs(x - i) <= 1 for i, x in enumerate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        ma = -1\n",
    "        for i in range(len(nums)):\n",
    "            if i >= 2:\n",
    "                ma = max(ma, nums[i - 2])\n",
    "            if nums[i] < ma:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        # 判断是否存在是全局倒置，但不是局部倒置的情况\n",
    "        n = len(nums)\n",
    "        for i in nums:\n",
    "            if abs(i-nums[i]) > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return True\n",
    "        \n",
    "        maxP = nums[0]\n",
    "        for i in range(2, n):\n",
    "            if nums[i] < maxP:\n",
    "                return False\n",
    "            maxP = max(maxP, nums[i-1])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n  < 3:\n",
    "            return True\n",
    "        leftmax = []\n",
    "        nowmax = 0\n",
    "        for i1 in range(n-2):\n",
    "            if nowmax < nums[i1]:\n",
    "                nowmax = nums[i1]\n",
    "            leftmax.append(nowmax)\n",
    "        rightmin = []\n",
    "        nowmin = n\n",
    "        for i2 in range(n-1,1,-1):\n",
    "            if nowmin > nums[i2]:\n",
    "                nowmin = nums[i2]\n",
    "            rightmin.append(nowmin)\n",
    "        return not any([i>j for i,j in zip(leftmax,rightmin[::-1])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        #第一种方法：\n",
    "        n = len(nums)\n",
    "        # g_counter = 0\n",
    "        # p_counter = 0\n",
    "        # for i in range(n - 1):\n",
    "        #     if nums[i] > nums[i+1]:\n",
    "        #         p_counter = p_counter + 1\n",
    "        #     print('p_counter:', p_counter)\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if nums[i] > nums[j]:\n",
    "        #             # return 1\n",
    "        #             # break\n",
    "        #             g_counter = g_counter +1\n",
    "        #             print('g:', g_counter)\n",
    "        #             if g_counter > p_counter:\n",
    "        #                 return any([])\n",
    "        #                 break\n",
    "        # #     print('g_counter:', g_counter)\n",
    "        # # return p_counter == g_counter\n",
    "        # return any([1])\n",
    "\n",
    "        #第二种方法：\n",
    "        # for i in range(n - 1):\n",
    "        #     for j in range(i+2, n):\n",
    "        #          if nums[i] > nums[j]:\n",
    "        #             return any([])\n",
    "        # return any([1])\n",
    "        #第三种方法：\n",
    "        # nums_old = nums[2:]\n",
    "        # nums_new = nums[:-2]\n",
    "        # print('old:', nums_old, 'new:', nums_new)\n",
    "        # for j in range(len(nums_new)):\n",
    "        #     for i in range(len(nums_new)):\n",
    "        #         print('长度：', len(nums_new),',   i:', i)\n",
    "        #         if nums_old[i] < nums_new[i]:\n",
    "        #             return any([])\n",
    "        #     nums_old = nums_old[1:]\n",
    "        #     nums_new = nums_new[:-1]\n",
    "        # print('old:', nums_old, 'new:', nums_new)\n",
    "        # return any([1])\n",
    "        #第四种方法：\n",
    "        mx = 0\n",
    "        for i in range(2, len(nums)):\n",
    "            mx = max(mx, nums[i - 2])\n",
    "            print(mx)\n",
    "            if mx > nums[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def isIdealPermutation(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        st = SortedList()\n",
    "        local_cnt = 0\n",
    "        global_cnt = 0\n",
    "        for i in range(n):\n",
    "            if(i+1<n and nums[i]>nums[i+1]):\n",
    "                local_cnt += 1\n",
    "            left, right = 0, len(st)-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums[i] > -st[mid]):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            global_cnt += right + 1\n",
    "            st.add(-nums[i])\n",
    "\n",
    "        return global_cnt == local_cnt\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
